package sword.offer;

/**
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，
 * 并且每个数字都在范围0～n-1之内。
 * 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 * 链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FiftyThree2 {
    // 通过对应关系求解  注意边界值 时间复杂度 O(n)
    class Solution {
        public int missingNumber(int[] nums) {
            int result = nums.length;
            for (int i=0; i<nums.length; i++){
                if (i != nums[i]){
                    result =  i;
                    break;
                }
            }
            return result;
        }
    }

    // 已经排序的数组 一般考虑使用二分法 时间复杂度 O(Log n)
    class Solution1 {
        public int missingNumber(int[] nums) {
            int right = nums.length-1, left = 0;
            while(left <= right){
                int mid = (left + right) / 2;
                if(nums[mid] == mid){ // 说明缺失数字在右边
                    left = mid + 1;
                }else{ // 说明缺失数字在左边
                    right = mid - 1;
                }
            }
            return left;
        }
    }

}
